package cn.icatw.leetcode.editor.cn;
//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。
//
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
//
//
//
// 示例 1：
//
//
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
//
// 示例 2：
//
//
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1]
//
// 示例 3：
//
//
//输入：nums = [], target = 0
//输出：[-1,-1]
//
//
//
// 提示：
//
//
// 0 <= nums.length <= 10⁵
// -10⁹ <= nums[i] <= 10⁹
// nums 是一个非递减数组
// -10⁹ <= target <= 10⁹
//
//
// Related Topics 数组 二分查找 👍 2641 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
public class T34{
    public static void main(String[] args) {

    }
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            //二分查找，先找出左边第一个匹配的元素，再从后往前找，直到找到第一个匹配的元素
            int leftIndex = leftIndex(nums, target);
            //-2为无元素匹配的情况
            if (leftIndex != -2&&nums[leftIndex+1]==target) {
                //leftIndex+1为元素下标
                //在数组中找到了元素
                int rightIndex = nums.length - 1;
                while (nums[leftIndex + 1] != nums[rightIndex] && rightIndex >= leftIndex + 1) {
                    rightIndex--;
                }
                return new int[]{leftIndex + 1, rightIndex};
            }
            return new int[]{-1, -1};
        }

        /**
         * 查询左边索引
         *
         * @param nums   数字
         * @param target 目标
         * @return int
         */
        private int leftIndex(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            int leftIndex = -2;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] >= target) {
                    right = mid - 1;
                    leftIndex = right;
                } else {
                    left = mid + 1;
                }
            }
            return leftIndex;
        }
    }
}

//leetcode submit region end(Prohibit modification and deletion)

